#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define random(x) (rand()%x)

using namespace std;

class Spirit{
	
public:
	Spirit()
	{
	
		quei=new int[m*n];
		quej=new int[m*n];
		prep=new int[m*n];
		head=0;
		rear=1;
		length=1;
		num=0;
		num1=0;
		quei[head]=1;
		quej[head]=1;
		prep[head]=-1;
		de=new int[300];
		
		quei1=new int[m*n];
		quej1=new int[m*n];
		prep1=new int[m*n];
		datai=new int[850];
		dataj=new int[850];
		queir=new int[m*n];
		quejr=new int[m*n];
		head1=0;
		rear1=1;
		length1=1;
		//quei1[head1]=20;
		//quej1[head1]=40;
		prep1[head1]=-1;
		
		
		//pos1=0;
	}
	
	~Spirit()
	{
	delete []quei1;
	delete []quej1;
	delete []prep1;
	
	delete []quei;
	delete []quej;
	delete []prep;
	delete []datai;
	delete []dataj;
	delete []queir;
	delete []quejr;
	}
	
	void new_space(int m1, int n1);//分配空间
	
	void delete_space(int m1);//释放空间
	
	void Maze_Runner();//移动精灵
	
	void Building_labyrinth();//创建迷宫
	
	void Path_finding_algorithm(int le,int cii,int cjj,int nii,int njj, int *queii,int *quejj,int *prepp,int headd,int poss,int rearr);//寻路算法
	void Path_finding_algorithm1(int le,int cii,int cjj,int nii,int njj, int *queii,int *quejj,int *prepp,int headd,int poss,int rearr);
private:
	int **p,**p1;//定义一个二维的int数组
	int *de;
	int m,n;
	int num;
	int num1;
	int *quei;//储存行坐标队列
	int *quej;//储存列坐标队列
	int *prep;//储存之前一步在队列中的位置
	
	int *quei1;//储存行坐标队列
	int *quej1;//储存列坐标队列
	int *prep1;//储存之前一步在队列中的位置

	int *queir;//储存行坐标队列
	int *quejr;//储存列坐标队列	
	int head,rear,length;//队列头，队列尾，队列长度
	int head1,rear1,length1;//队列头，队列尾，队列长度   
	int pos;//当前节点在队列中的位置
	int pos1;
	int ci,cj,ni,nj;//当前节点坐标 新节点坐标
	int ci1,cj1,ni1,nj1;//当前节点坐标 新节点坐标
	int dir;//移动方向
	
	int *datai;
	int *dataj;
	
	
};


	 /* 分配空间*/
void Spirit::new_space(int m1, int n1)
{
	m=m1;
	n=n1;
	//
	//创建行指针
	p=new int*[m+2];
	p1=new int*[m+2];
	//为每一行分配空间
	for(int i=0;i<=m+1;i++)
	{
	p[i] = new int [n+2];
	p1[i] = new int [n+2];
	}
}
/*释放空间*/
void Spirit::delete_space(int m1)
{
	m=m1;
	
	for(int i=0;i<=m+1;i++){
		
		delete[] p[i];
		delete[] p1[i];
	}
		delete[] p;
		delete[] p1;

}

/*创建迷宫*/
void Spirit::Building_labyrinth()
{
	srand((int)time(0));
	for(int i=0;i<=m+1;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			if(i==0|j==0|i==m+1|j==n+1)
			{
				p[i][j]=1;
				p1[i][j]=1;
			}
			else
			{
				int x=random(50);
				if(x<=1)

					{
					p[i][j]=1;
					p1[i][j]=1;
				}
				else
				{
					p[i][j]=0;
					p1[i][j]=0;
				}	
			}
				
				
				
				
		}		
				
	}
} 
/*寻路算法*/
void Spirit::Path_finding_algorithm(int le,int cii,int cjj,int nii,int njj, int *queii,int *quejj,int *prepp,int headd,int poss,int rearr)
{
	int move[8][2] = {0,1,1,0,0,-1,-1,0,-1,-1,-1,1,1,-1,1,1} ;
	if(p[1][1]==1)//第一点为1无法通过
		le=0;
	else
		p[1][1]=2;

	while(le)//队列不为空则继续
	{
		cout<<"le="<<le<<endl;
		for(poss=headd;poss<headd+le;poss++)//遍历所有节点
		{
			//cout<<"headd"<<headd<<endl;
			//cout<<"le"<<le<<endl;
			cii=queii[poss];cjj=quejj[poss];//当前位置坐标 
			datai[poss]=queii[poss];
			dataj[poss]=quejj[poss];
			// cout<<"poss"<<poss<<endl;
			 //cout<<"cii cjj" <<"("<<cii<<","<<cjj<<")"<<endl;
			num1++;
			
			 if(cii==m&&cjj==n)
				break;
			
			for(dir=0;dir<8;dir++)//寻找八个方向
			{                                                                                                                                                         
				nii=cii+move[dir][0];njj=cjj+move[dir][1];
				if(p[nii][njj]==0)//假如没有走过
				{
					queii[rearr]=nii;quejj[rearr]=njj;prepp[rearr]=poss;//新节点入队
					rearr=rearr+1;
					 p[nii][njj]=2;//标记已经走过
				}
	
			} 
		}
		
		if(cii==m&&cjj==n)
			break;
			headd=headd+le;
			le=rearr-headd;//节点出列

	}
	
	if(cii==m&&cjj==n)
	{
		while(poss!=-1)
		{
			cout<<'('<<queii[poss]<<','<<quejj[poss]<<')';
			
			poss=prepp[poss];
			if(poss!=-1)
				cout<<',';
			//cout<<"poss"<<poss;
			de[num]=poss;
			num++;

		}
		cout<<endl;
	}
	else
	{
		cout<<"无路可走1"<<endl;
	}
	
	
}

void Spirit::Path_finding_algorithm1(int le,int cii,int cjj,int nii,int njj, int *queii,int *quejj,int *prepp,int headd,int poss,int rearr)
{
	int move[8][2] = {0,1,1,0,0,-1,-1,0,-1,-1,-1,1,1,-1,1,1} ;
	if(p[m][n]==1)//第一点为1无法通过
	{
		le=0;
		cout<<"p[m][n]"<<p[m][n];
	}
	else
		p[m][n]=3;
	poss=0;
		for(int i=num1-1;i>0;i--)
		{
			queii[poss]=datai[i];
			quejj[poss]=dataj[i];
			poss++;
			
		} 
		for(int j=0;j<=poss;j++)
		{
			//cout<<"queii[poss]" "quejj[poss]"<<"("<<queii[j]<<","<<quejj[j]<<")"<<endl;
			//cout<<"poss"<<j<<endl;
		}
			
	 //while(le)//队列不为空则继续
	//{

		  for(poss=head;poss<num1-1;poss++)//遍历所有节点
		 {
			 cii=queii[poss];cjj=quejj[poss];//当前位置坐标
			// cout<<"poss="<<poss<<endl;
			// cout<<"queii[poss] quejj[poss]" <<"("<<queii[poss]<<","<<quejj[poss]<<")"<<endl;
			 if(cii==1&&cjj==1)
			 break;
			 for(dir=0;dir<8;dir++)//寻找八个方向
			 {                                                                                                                                                        
				 nii=cii+move[dir][0];njj=cjj+move[dir][1];
				 if(p[nii][njj]!=1||p[nii][njj]!=3)//假如没有走过
				 {
				 queir[rearr]=nii;quejr[rearr]=njj;prepp[rearr]=poss;//新节点入队
				// cout<<" queii[rearr]  quejj[rearr]"<<"("<<queii[rearr]<<","<<quejj[rearr]<<")"<<endl;
				 rearr=rearr+1;
				 p[nii][njj]=3;//标记已经走过
				 }
			 }
		
		// }
		 if(cii==1&&cjj==1)
			 break;
			 headd=headd+le;
			 le=rearr-headd;//节点出列	
	} 
	if(cii==1&&cjj==1)
	{
		while(poss!=-1)
		{
		//	cout<<'('<<queir[poss]<<','<<quejr[poss]<<')'<<endl;
			
			poss=prepp[poss];
			if(poss!=-1)
				//cout<<',';
			//cout<<"poss"<<poss;
			de[num]=poss;
			num++;

		}
		cout<<endl;
	}
	else
	{
		cout<<"无路可走"<<endl;
	}
	
	
}



/*移动精灵*/
void Spirit::Maze_Runner() 
{
	
		Path_finding_algorithm(length,ci,cj,ni,nj,quei,quej,prep,head,pos,rear);
		//Path_finding_algorithm1(length1,ci1,cj1,ni1,nj1,quei1,quej1,prep1,head1,pos1,rear1);
			for(int k=num;k>-1;k--)
			{	
				pos=de[k];
				//pos1=de[num-k];
				for(int i=0;i<=m+1;i++)
				{
						for(int j=0;j<=n+1;j++)
						{
							if(p1[i][j]==0)
							{ 
								if(quei[pos]==i&&quej[pos]==j)//当前位置坐标
								{
									cout<<"\033[41m1\033[m";
									p1[i][j]=2;
								} 
								if(quei[pos1]==i&&quej[pos1]==j)
								{
									
									cout<<"\033[42mA\033[m";
									p1[i][j]=3;
								}
								
								if(!p1[i][j]==1)
								cout<<" ";	
							}
							else if(p1[i][j]==2)
								cout<<" ";
							else if(p1[i][j]==3)
								cout<<" ";
							else
								cout<<"#";
							   
						}
						cout<<endl;
				}
				sleep(1);
			}
			cout<<"Game over!!"<<endl;
	
	
	//cout<<"\033[0;0H";
}

int main()
{
	//定义一个精灵对象
	Spirit Smurfs;
	int m1,n1;
	cout<<"请输入迷宫规格：";
	cin>>m1>>n1;
	
	Smurfs.new_space(m1,n1);
	
	Smurfs.Building_labyrinth();
	
	Smurfs.Maze_Runner();

	Smurfs.delete_space(m1);
	
	return 0;
}
